//Sunday, November 29 2009
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class AddElectricalWires
{
public:
	int maxNewWires(vector <string> wires, vector <int> gridConnections)
	{
		int ret = 0;
		int connection = 0;
		n = wires.size();
		memset(mark, false, sizeof(mark));
		memset(a, false, sizeof(a));
		for(int i=0; i<n; i++)
			for(int j=0; j<n; j++)
				if (a[i][j] = wires[i][j]=='1')
					connection++;	//The connections already exist.
		connection /= 2;
		int left = n;	//The node has no connection by now.
		int mxcomp = 0;
		for(int i=0; i<gridConnections.size(); i++)
		{
			curcnt = 0;
			dfs(gridConnections[i]);
			ret += curcnt*(curcnt-1)/2;
			left -= curcnt;
			mxcomp=max(mxcomp,curcnt);
		}
		ret += left*(left-1)/2+mxcomp*left;
		return ret-connection;
	}
	int n;
	bool a[128][128];	//The wires exist or not.
	bool mark[128]; //The nodes has been visited or not.
	int curcnt; // Count how many nodes it traversed.
	void dfs(int v)
	{
		if (mark[v]) return;
		mark[v]=true;
		curcnt++;
		for(int i=0; i<n; i++)
			if (a[v][i])
				dfs(i);
	}
};
